package com.example.tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 *
 *  示例 1：
 * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
 *            5
 *          /   \
 *         4     8
 *        /     / \
 *       11    13  4
 *      /  \        \
 *     7    2        1
 * 输出：[[5,4,11,2],[5,8,4,5]]
 *
 *  示例 2：
 * 输入：root = [1,2,3], targetSum = 5
 * 输出：[]
 *
 *  示例 3：
 * 输入：root = [1,2], targetSum = 0
 * 输出：[]
 */
public class Leetcode113_PathSumII {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right = new TreeNode(8);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.left = new TreeNode(5);
        root.right.right.right = new TreeNode(1);
        List<List<Integer>> ress;

        ress = new Solution().pathSum(root, 22);

        ress.forEach(res -> {
            Integer[] integers = res.stream().toArray(Integer[] :: new);
            System.out.println(Arrays.toString(integers));
        });


//        root = new TreeNode(-2);
//        root.right = new TreeNode(-3);
//        ress = new Solution().pathSum(root, -5);
//        ress.forEach(res -> {
//            Integer[] integers = res.stream().toArray(Integer[] :: new);
//            System.out.println(Arrays.toString(integers));
//        });

        ress = new Solution().pathSum(null, 1);
        ress.forEach(res -> {
            Integer[] integers = res.stream().toArray(Integer[] :: new);
            System.out.println(Arrays.toString(integers));
        });



    }

    static class Solution {

        private List<List<Integer>> pathSum2(TreeNode root, int targetSum) {
            List<List<Integer>> res = new ArrayList<>();

            return res;
        }

        /**
         * DFS + 回溯
         * @param root
         * @param targetSum
         * @return
         */
        private List<List<Integer>> pathSum1(TreeNode root, int targetSum) {
            List<List<Integer>> ress = new LinkedList<>();

            dfs(root, targetSum, ress , new LinkedList<>());

            return ress;
        }

        private void dfs(TreeNode root, int targetSum, List<List<Integer>> ress, LinkedList<Integer> singleRes) {
            if (root == null) return;

            // 不能进行剪枝，因为可能有负数(只适用于全是正数的情况)
//            singleRes.offerLast(root.val);
//            if (targetSum - root.val != 0) {
//                if (root.left != null) {
//                    dfs(root.left, targetSum - root.val, ress, singleRes);
//                    singleRes.pollLast();
//                }
//
//                if (root.right != null) {
//                    dfs(root.right, targetSum - root.val, ress, singleRes);
//                    singleRes.pollLast();
//                }
//            } else {
//                if (root.left == null && root.right == null) {
//                    ress.add(new LinkedList<>(singleRes));
//                    return;
//                }
//            }

            singleRes.offerLast(root.val);
            if (targetSum - root.val == 0 && root.left == null && root.right == null) { // 到了根节点并且满足路径和为 targetSum
                ress.add(new LinkedList<>(singleRes)); //必须先 new 一个新 List再去添加,不然后面再去操作同一个 list 会将前面的数据覆盖
            }

            dfs(root.left, targetSum - root.val, ress, singleRes);
            dfs(root.right, targetSum - root.val, ress, singleRes);
            singleRes.pollLast();

        }

        public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
            return pathSum1(root, targetSum);
        }
    }
}
